class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        length1 = len(s)
        length2 = len(p)

        dp = [[False for _ in range(length1 + 1)] for _ in range(length2 + 1)]
        dp[0][0] = True
        for i in range(1, length2 + 1):
            if p[i-1] == '*': dp[i][0] |= dp[i-1][0]
            for j in range(1, length1 + 1):
                if p[i-1] == s[j-1] or p[i-1] == '?' or p[i-1] == '*':
                    dp[i][j] = dp[i-1][j-1]
                if p[i-1] == '*':
                    dp[i][j] |= dp[i][j-1]
                    dp[i][j] |= dp[i-1][j]
        return dp[length2][length1]


if __name__ == '__main__':
    s = Solution()
    r = s.isMatch( "abcabczzzde","*abc???de*")
    print(r)